#include <vector>
#include<array>

class Solution {
public:
    bool possibleToStamp(std::vector<std::vector<int>>& grid, int stampHeight, int stampWidth) {
        size_t n = grid.size();
        size_t m = grid[0].size();
        std::vector<std::vector<int>> sum(n+1, std::vector<int>(m+1));
        std::vector<std::vector<int>> sum2(n+2, std::vector<int>(m+2));

        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                sum[i+1][j+1] = grid[i][j];
            }
        }
        
        cal(sum,n,m);

        for (int a=1,c=a+stampHeight-1;c<=n;a++,c++)
        {
            for (int b=1,d=b+stampWidth-1;d<=m;b++,d++)
            {
                if ( cal2(sum,a,b,c,d)==0)
                {
                    buildMatrix(sum2,a,b,c,d);
                }
            }
        }
        cal(sum2,n+1,m+1);
        for (int i=0;i<n;i++)
        {
            for (int j=0;j<m;j++)
            {
                if (grid[i][j]==0&&sum2[i+1][j+1]==0)
                    return false;
            }
        }
        return true;
    }
    
    void cal(std::vector<std::vector<int>>& matrix,int n , int m)
    {
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
            {
                matrix[i][j] += matrix[i][j-1]+matrix[i-1][j]-matrix[i-1][j-1];
            }
        }
    }
    
    void buildMatrix(std::vector<std::vector<int>>& matrix,int a,int b,int c, int d)
    {
      
        matrix[a][b] ++ ;
        matrix[c+1][b]--;
        matrix[a][d+1]--;
        matrix[c+1][d+1]++;
    }
    
    int cal2(std::vector<std::vector<int>>& matrix,int a,int b,int c, int d)
    {
        return matrix[c][d] - matrix[c][b-1] - matrix[a-1][d] +matrix[a-1][b-1];
    }
    
};